perm filename CMPARE[0,BGB] blob
sn#116864 filedate 1974-08-30 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00006 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 {F1F2F3F4⊂C<NαCOMPARING.λ30P95I425,0JCFA} SECTION 8.
C00008 00003 ⊂8.1 A Polygon Matching Method.⊃
C00015 00004 ⊂8.2 Geometric Normalization of Polygons.⊃
C00019 00005 ⊂8.3 Compare by Recursive Windowing.⊃
C00021 00006 ⊂8.4 Related Work and Work Yet To Be Done.⊃
C00023 ENDMK
C⊗;
{F1;F2;F3;F4;⊂C;<N;αCOMPARING.;λ30;P95;I425,0;JCFA} SECTION 8.
{JCFD} IMAGE COMPARING.
{λ10;W250;JAFA}
8.0 Introduction to Image Comparing.
8.1 A Polygon Matching Method.
8.2 Geometric Normalization of Polygons.
8.3 Compare by Recursive Windowing.
8.4 Related Work and Work Yet To Be Done.
{λ30;W0;I950,0;JU;FA}
⊂8.0 Introduction to Image Comparing.⊃
The image compare process is both the <"keystone of the
arch"> as well as the <"weakest link of the chain">. By comparing
images, the 3-D modeling and the 2-D image processing are finally
linked, however as will be apparent the implementation to date
demonstrates only a small part of what is possible. In the feedback
perception design, there are three classes of compare operations:
verification, revelation and recognition which may be applied to
each of the three kinds of image data structures: raster, contour and
mosaic. The verify compare finds the corresponding entities between
a predicted image and a perceived image for the sake of calibration
measurement and for the sake of eliminating already known features
from further consideration. In vision for industrial machine
assembly, calibration measurements suddenly seems to be the only kind
of vision necessary in a relatively constrained
factory situation. The reveal compare
involves finding the corresponding entities in two perceived images,
so that the location and extent of new objects can be solved.
Finally, the recognition compare involves matching a perceived
entity with one of a set of prototype entities.
From the view point of modeling the lowest level compare
operation should somehow be arranged to be a one to one template
match rather than a multi dimensional statistical discrimination or a
graph isomorphism test. That is if the entities to be matched are
incommensurate, the model designer censures the model that generated
an unrealistic prediction rather than the pattern matcher which
cannot see a vague resemblance. Clearly this position should not be
taken to an extreme and the present system could be enhanced by the
inclusion of an appropriate collection of traditional pattern
matching techniques. However, two techniques of commensuration that
are naturally the responsibility of a model builder are geometric
normalization and topological segmentation. Geometric normalization
involves eliminating the irrelevant geometric differences such as location,
orientation and scale. Topological segmentation involves subdividing
a complex object into pieces, (perhaps even canonical pieces) so
that only simple small parts need be matched (that is the compare
becomes recursive). The remainder of this chapter explains a method
for matching structured images consisting of polygons. The most
original part of the method involves finding the correspondence,
illustrated in Figure 8.1, for polygonal figures that fission or
fuse from one image to the next.
{I∂12,0;JCFC} FIGURE 8.1 - EXAMPLE OF POLYGON FUSION COMPARE.
{X.615;H2;I∂-120,15;⊗CMPAR1.PLT;I∂0,615;⊗CMPAR2.PLT;
X0.95;I∂715,630;*CMPAR4.PLT;JUFAQ}
⊂8.1 A Polygon Matching Method.⊃
The image compare process in CRE, connects the polygons and
vectors of one image with corresponding polygons and vectors of another
image. CRE's compare solves the problem of correlating polygons
between two similar images and is composed of four steps:
{λ10;JA}
1. Compute polygonal lamina inertia tensors, <lamten nodes>.
2. Compare and connect polygons one to one at corresponding levels of the nested polygon tree.
3. Compare and connect polygons two to one at corresponding levels of the nested polygon tree.
4. Compare and connect vertices of connected polygons using recursive windowing.
{λ30;JU}
First, the lamina inertia tensor nodes (called <lamten>'s) of
all the polygons of an image are computed. A lamten node contains
the center of mass as well as the tensor of a polygon. The meaning
of the inertia tensor is that it characterizes each polygon as a
rectangle of a certain length and width at a particular location and
orientation; and of further importance such inertia tensors can be
added to characterize two or more polygons by a single rectangle. It
is the lamten rectangles that provide a basis for normalization.
Second, all the lamtens of the polygons of one level of the
first image are compared with all the lamtens of the polygons of the
corresponding level of the second image for nearly exact match. The
potentially (M*N/2) compares is avoided by sorting on the center of
mass locations. In CRE, which is intended for comparing sequences
of pictures of natural scenes; match for center of mass location is
tested first and most strictly, followed by match for inertia.
Pointers between matching polygons are placed in two link positions
of the polygon nodes and the polygons are considered to be matched.
Third, all the unmated polygons of a level are considered
two at a time and a fusion lamten node for each pair is made. The
potentially (N*N/2-N) fusion lamtens are avoided because there is a
maximum possible unmated inertia in the other image; if there are no
unmated polygons in one image then the extra polygons of the first
image can be ignored. In the event where there are unmated polygons
in corresponding levels of the two images, the multi-polygon fusion
lamten of one are compared with the single polygon lamten of the
other. The fusion (fission) compare solves the rather nasty problem,
of linking two contour polygons of one image with a single contour
polygon in the next image.
Fourth, the vertices of mated polygons are in turn compared
and mated. To start a vertex compare, the vertices of one polygon
are translated, rotated and dilated to get that polygon's lamten
rectangle coincident with its mate (or mates). Conceptually, each
vertex of one polygon is compared with each vertex of the other
polygon(s) and the mutually closest vertices (closer than an epsilon)
are considered to be mated. Actually the potential (N*M) compares
are avoided by a recursive windowing scheme similar to that used in
hidden line elimination algorithms. The compare execution takes less
than a second on images such as the pump base (Figures 0.3 and 0.4)
blocks (Figure 8.1) and a doll (Figure 8.2). The doll's silhouette is
headless when viewed from the backside because its hair is black.
{FCJC} FIGURE 8.2 - EXAMPLE OF VERTEX MATCHING.
{X0.95;I∂220,630;H2;*CMPAR3.PLT;I∂400,0;JUFA}
⊂8.2 Geometric Normalization of Polygons.⊃
The lamina inertia tensor of a polygon with N sides is
computed by summation over N trapezoids. The trapezoid corresponding
to each side is formed by dropping perpendiculars <up> to the top of
the image frame; each such trapezoid consists of a rectangle an a
right triangle; since the sides of polygons are directed vectors the
areas of the triangles and rectangles can be arranged to take
positive and negative values such that a summation will describe the
interior region of the polygon as positive. The equations necessary
for computing the lamina inertia tensor of a polygon were derived
from material in (Goldstein 1950).
{λ8;JA}
RECTANGLE'S LAMINA INERTIA TENSOR ABOUT ITS CENTER OF MASS.
MXX ← B*B*AREA/12; (B HEIGHT IN ROWS).
MYY ← A*A*AREA/12; (A WIDTH IN COLUMNS).
MZZ ← MXX + MYY;
PXY ← 0;
ORIENTED RIGHT TRIANGLE'S LAMINA INERTIA TENSOR ABOUT ITS CENTER OF MASS.
MXX ← B*B*AREA/18; (B HEIGHT IN ROWS).
MYY ← A*A*AREA/18; (A WIDTH IN COLUMNS).
MZZ ← MXX + MYY;
PXY ← -A*B*AREA/36;
SUMMATION OF LAMINA INERTIA TENSORS.
AREA ← (AREA1 + AREA2);
XCM ← (AREA1 * XCM1 + AREA2 * XCM2) / AREA;
YCM ← (AREA1 * YCM1 + AREA2 * YCM2) / AREA;
MXX ← MXX1 +YCM1*YCM1*AREA1 +MXX2 +YCM2*YCM2*AREA2 -YCM*YCM*AREA;
MYY ← MYY1 +XCM1*XCM1*AREA1 +MYY2 +XCM2*XCM2*AREA2 -XCM*XCM*AREA;
PXY ← PXY1 -XCM1*YCM1*AREA1 +PXY2 -XCM2*YCM2*AREA2 +XCM*YCM*AREA;
ANGLE OF PRINCIPLE AXIS
The angle of the principle axis, PHI, lies in the interval -π/2 to π/2.
PHI ← 0.5*ATAN(2*PXY/(MYY-MXX));
PXY ← 0.5*(MYY - MXX)*TAN(2*PHI);
TRANSLATION OF LAMINA INERTIA TENSOR AWAY FROM CENTER OF MASS.
MXX' ← MXX + AREA*DY*DY;
MYY' ← MYY + AREA*DX*DX;
PXY' ← PXY - AREA*DX*DY;
ROTATION OF LAMINA INERTIA TENSOR ABOUT CENTER OF MASS.
C ← COSINE(PHI);
S ← SINE(PHI);
MXX' ← C*C*MXX + S*S*MYY - 2*C*S*PXY;
MYY' ← C*C*MYY + S*S*MXX + 2*C*S*PXY;
PXY' ← (C*C - S*S)*PXY + C*S*(MYY - MXX);
{λ30;JUQ}
⊂8.3 Compare by Recursive Windowing.⊃
The final step in the CRE polygon match (Section 8.1) is
to link the corresponding vertices between two geometrically
normalized polygons (or sets of polygons) using a nearest neighbor
criterion. The nearest neighbors are found by recursive windowing,
initially all the vertices are pushed into one large window which is
subsequently split until there were few enough vertices contained in
the window to allow exhaustive comparing. To make this windowing
technique applicable to the nearest neighbor problem a distance
criterion, <delta>, has to be declared so that the windows overlap by
that amount. Consequently the windows are no longer disjoint
rectangles, but are rather boxes with rounded corners, the smallest
possible window being a circle with radius, <delta>. The recursive
windowing technique is essentially a two dimensional partition sort,
the technique can be generalized for comparing edges and other
entities in 2-D or higher dimensions.
⊂8.4 Related Work and Work Yet To Be Done.⊃
To complete the visual feedback system, there remains yet to
be written an image compare that uses both raster based and polygon based
techniques. The two kinds of compares are symbiotic in that the
polygon compare could aim the raster correlator alleviating the need
to do bulk correlation over wide areas, and the raster correlator
could verify and improve the measurement of corresponding vertex
loci. At Stanford, image comparison by raster correlation techniques
is begin worked on by Quam(71), Hannah and Morevac. Another approach
to comparing polygons is to examine their curvature, the curvature of
a polygon can be expressed as a parametric function of arc length;
two such functions can be normalized and alligned and differenced
using statistical techniques (Zahn 66).